import java.util.*;

public class Test3 {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map=new HashMap<>();
        //统计单词出现的次数
       for(String word:words){
           if(map.get(word)==null){
               map.put(word,1);
           }else{
               int val=map.get(word);
               map.put(word,val+1);
           }
       }
       //成为Top-k问题，创建小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
       //遍历map
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue().compareTo(entry.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                }
                if(top.getValue().compareTo(entry.getValue())==0){
                    if(top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }

            }
        }
        //此时的大根堆里面一定是前k个高频单词
        List<String> list=new ArrayList<>();
        for(int i=0;i<k;i++){
                Map.Entry<String,Integer> tmp=minHeap.poll();
                list.add(tmp.getKey());
        }
        //Collections专门用来处理集合
        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {

    }
}
